package m_HashTable;

import java.util.Arrays;
import java.util.Random;
import java.util.TreeMap;

public class HashTable_try<K extends Comparable<? super K>, V> {
	
	private static final int[] capacity = {53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
											49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469,
											12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741};
	
	private static final int upperVal = 10, lowerVal = 2;
	private int size = 0, capacityIndex = 0, M = 53;
	
	private TreeMap<K, V>[] data;  
//	private TreeMap[] data;		泛型类都可以扔掉泛型拿来用，默认会用object类型来包容任何类型，但是例如get(key)方法，返回值要V类型，这时候就掉链子了，不带泛型我只能拿到object

	public HashTable_try() {
		data = new TreeMap[M]; //TreeMap并不是接口类型，而是说java的泛型只是编译机制，通过反编译查看class文件也可以发现 并没有泛型的存在；
//		Arrays.fill(data, new TreeMap<>()); //相对于默认值 初始化总不会错；但是，这样是大错特错的，因为fill是赋予的重复值，是一次计算后对范围内每一个数组元素都赋上指定值，所以这里会导致每个数组项都指向同一个数组，如果有疑问可以解开测试一下；

//		for (TreeMap i : data) {   //这里也不能用foreach赋值，事实证明foreach对全null的数组还是会迭代每一个元素;
//			i = new TreeMap<>();  				还是引用的问题
//		}					↑等价↓
//							for(int k = 0 ; k < M ; k ++){   
//		    					TreeMap<K, V> i = hashtable[k];
//		    					i = new TreeMap<>();  
//							}
		for (int i = 0; i < data.length; i++) {  
			data[i] = new TreeMap<>();
//			data[i] = new TreeMap();
		}
	}
	// 因为容量是预设的，就不开放指定容量的构造函数了
	
	private int hash(K key) {
		return ( key.hashCode() & 0x7fffffff ) % M;
	}
	
	public int getSize() {  //开放的都是用户接口
		return size;
	}
	
	//之后就是传统的增删改查
	public void add(K key, V value) {
		TreeMap<K, V> target = data[hash(key)];
		if(target.containsKey(key))
			target.put(key, value);
		else {
			target.put(key, value);
			size ++;
			
			if(size >= upperVal*M && capacityIndex+1 < capacity.length )
				resize(++capacityIndex);
		
		}
	}
	
	public V remove(K key) {
		TreeMap<K, V> target = data[hash(key)];
		V temp = target.remove(key);
		if( temp == null ) {   //没有这个key或者key映射的值就是null 都会return null，但size的操作对于这两种情况是不统一的；
			if(target.containsKey(key))
				size--;
			return null;
		}
		else {
			size --;
			if(size <= lowerVal*M && capacityIndex-1 >= 0 ) 
				resize(--capacityIndex);
			
			return temp;
		}
	}
	
	public void set(K key, V value) {
		TreeMap<K, V> target = data[hash(key)];
		
		assert target.size() > 0;  //key !exist
		target.put(key, value);
	}
	
	public V get(K key) {
		TreeMap<K, V> target = data[hash(key)];
		return target.get(key);  //没有就返回null
	}
	
	public boolean contains(K key) {
		return data[hash(key)].containsKey(key);
	}
	
	//这种resize的思路比bobo的差，一开始还出了bug；在做任何一项任务时，一定要先面向目标面向任务本身来解决，复用一些看似简单的方法时，一定要注意该方法有没有非面向目标的不必要的操作，如果不注意很可能会出现bug；
	private void resize(int newCapacityIndex) {
		TreeMap<K, V>[] newData = new TreeMap[capacity[newCapacityIndex]]; //虽然是接口类型 但是只要其实际引用的 是目标类型即可；

		TreeMap<K, V>[] oldData = this.data;
		this.data = newData;
		for (int i = 0; i < data.length; i++) {  
			data[i] = new TreeMap<>();
		}
		
		this.capacityIndex = newCapacityIndex;
		int oldSize = this.size;

		int oldM = this.M;
		this.M = data.length;
		for(int i = 0 ; i < oldM ; i ++) {
			for (K key : oldData[i].keySet()) {
				add(key, oldData[i].get(key));          //复用方法来转移值的时候一定不能只看语意，add里面还不断维护了size，其实这是个没必要的操作，造成了size的错误，翻了一番；
			}
		}
		this.size = oldSize;  //***至关重要的一步**   
		//size实际不变，这里调用了add去添加数据就会有多维护size的问题，也可以不调add，直接添加
	}

	@Override
	public String toString() {
		return "HashTable_try [size=" + size + ",capa="+ M + ", data=" + Arrays.toString(data) + "]";
	}

	public static void main(String[] args) {
		HashTable_try<Integer, Integer> test = new HashTable_try<>();
//		for (int i = 0; i < 16; i++) {
//			test.add(i, i%5);
//		}
		for (int i = 0; i < 1000; i++) {
			test.add(i, i%20);
		}
		System.out.println(test);
		
	}
	
}
